package LeetCode;

public class LC_668_KthSmallestNumberinMultiplicationTable {

    public static void main(String[] args) {

    }

    class Solution {
        public int findKthNumber(int m, int n, int k) {
            int low = 1, high = m * n;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                int cnt = countEqualLess(m, n, mid);
                if (cnt < k) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return low;
        }

        private int countEqualLess(int m, int n, int val) {
            int cnt = 0;
            for (int i = 1; i <= m; i++) {
                cnt += Math.min(n, val / i);
            }
            return cnt;
        }
    }
}